Luogu P1120 小木棍【数据加强版】

Posted on | In |
Words count in article: 448 | Reading time ≈ 2

暴力搜索+剪枝

（这题简直神级剪枝）

由于200~1000ms实在坑人（实际上最后T的几乎都是500和1000的数据）

所以卡了我很久……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
#define N 10010
using namespace std;
int n,len[N],l,cnt,sum;
bool used[N];
bool mmp(int x,int y)
{
    return x>y;
}
void dfs(int x,int y,int lent,int goal,int now)//记录当前的这根小木棍
{
    if(x>sum/goal)
    {
        printf("%d",goal);
        exit(0);
    }
    if(goal-lent<len[cnt])
        return;//如果连最小的填进去都会大于当前答案的话就回溯
    for(int i=now;i<=cnt;i++)//从当前开始枚举，因为前面的一定被枚举过了，再做就是浪费时间
    {
        if(!used[i]&&lent+len[i]<=goal)
        {
            used[i]=true;
            lent+=len[i];
            if(lent==goal)
                dfs(x+1,1,0,goal,1);
            else
                dfs(x,y+1,lent,goal,i+1);
            used[i]=false;
            lent-=len[i];
            if(lent+len[i]==goal||lent==0)
                break;//如果这一组可以凑出却不是正确答案或者第一根都无法满足就直接退出，没必要再去枚举更小的来代替它，因为这一根总是要被用的。
            while(len[i]==len[i+1])
                i++;//该长度若不可行，则同样长度的也不可行
        }
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&l);
        if(l>50)
            continue;//一定要优先过滤50+的数据
        len[++cnt]=l;
        sum+=len[cnt];
    }
    sort(len+1,len+1+cnt,mmp);//从大到小排序，方便搜索与剪枝
    for(int i=len[1];i<=sum/2;i++)
        if(sum%i==0)
            dfs(1,1,0,i,1);//从小到大枚举答案，遇到一个可直接跳出
    printf("%d",sum);
    return 0;
}

参考了许多题解大佬，从9分到21分到33分到36分到63分到66分到AC……

而且跑的很慢QwQ

1100ms

0%